package com.flower.algorithm.recursion;

/**
 * @ClassName Maze
 * @Description 递归问题
 * @Author 吃麻椒的花酱
 * @Date 2022/1/9 12:54
 * @Version 1.0
 */

/*
递归需要遵守的重要规则
  执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
  方法的局部变量是独立的，不会相互影响, 比如n变量
  如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
  递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死归了
  当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
*/

public class Maze {
    public static void main(String[] args) {
        int[][] maze=new int[8][8];
        for (int i = 0; i < 8; i++) {
            maze[0][i]=1;
            maze[7][i] =1;
            maze[i][0]=1;
            maze[i][7]=1;
        }
        maze[3][1]=1;
        maze[3][2] = 1;
        setWaypoint(maze,1,1);
       for (int i = 0; i < maze.length; i++) {
           for (int j = 0; j < maze[0].length; j++) {
               System.out.print(maze[i][j]+" ");
           }
           System.out.println();
       }
    }
    /**
     * @author 吃麻椒的花酱
     * @date 2022/1/9 13:05
     * @Description 0表示未走，1表示边框，2表示可以走，3表示走不通
     * @param map 迷宫
     * @param i
     * @param j
     * @return boolean
     */
    public static boolean setWaypoint(int[][] map,int i,int j){
        if(map[6][6]==2){
            return true;
        }else {
            if (map[i][j]==0){
                map[i][j]=2;
                if(setWaypoint(map,i+1,j))
                    return true;
                else if (setWaypoint(map, i, j+1))
                    return true;
                else if (setWaypoint(map, i-1, j))
                    return true;
                else if(setWaypoint(map,i,j-1))
                    return true;
                else
                {
                    map[i][j]=3;
                    return false;
                }
            }
            else {
                return false;

            }
        }
    }
}
